package chapter02;

import java.util.ArrayList;
import java.util.List;

public class Insert57 {
    /**
     * 将新区间插入到列表中区间 分为三种情况
     * 找到旧列表中插入新区间位置后 将旧列表其他位置区间直接加入新列表即可
     * i->[0,length-1]
     * left=intervals[i][0];
     * right=intervals[i][1];
     * 1) newInterval[1]<left 新区间在旧列表当前区间左边
     *    将新区间直接加入新列表
     *    从旧列表当前区间开始依次加入到新列表
     * 2) newInterval[0]>right 新区间在旧列表当前区间右边
     *    将旧列表当前区间加入新列表
     *    i++ 继续遍历旧列表下一个区间
     * 3) newInterval[0]<=right 新区间左边界在旧列表当前区间右边界左边
     *    left=newInterval[0]<left?newInterval[0]:left 合并区间左边界是在当前区间左边还是当前区间左边界
     *    a) newInterval[1]<=right 新区间右边界不超过旧列表当前区间右边界
     *       合并区间 [left,right]
     *       i++ 从旧列表当前区间开始依次加入到新列表
     *    b) 新区间右边界超过旧列表当前区间右边界 遍历旧列表区间 找到新区间右边界在遍历区间左边的当前区间
     *       right=newInterval[1]>intervals[i-1][1]?newInterval[1]:intervals[i-1][1] 合并区间右边界
     *       合并区间 [left,right]
     *       i++ 从旧列表当前区间开始依次加入到新列表
     *  退出循环来到的是需要加入到新列表的区间
     *  注意点：若新区间插入到旧列表末尾 循环会忽略这种情况
     *    特别判断：newInterval[0]>right 新区间左边界在旧列表当前区间右边
     *             手动加入新区间 list.add(new int[]{newInterval[0],newInterval[1]});
     */
    public int[][] insert(int[][] intervals, int[] newInterval) {
        if(intervals.length<1){
            return new int[][]{{newInterval[0],newInterval[1]}};
        }
        int left=intervals[0][0];
        int right=intervals[0][1];
        int i=0;
        List<int[]> list=new ArrayList<>();
        while (i<intervals.length){
            left=intervals[i][0];
            right=intervals[i][1];
            if(newInterval[1]<left){
                list.add(new int[]{newInterval[0],newInterval[1]});
                break;
            }else if(newInterval[0]<=right){
                left=newInterval[0]<left?newInterval[0]:left;
                if(newInterval[1]<=right){
                    list.add(new int[]{left,right});
                    i++;
                    break;
                }else{
                    i++;
                    while(i<intervals.length&&newInterval[1]>=intervals[i][0]){
                        i++;
                    }
                    right=newInterval[1]>intervals[i-1][1]?newInterval[1]:intervals[i-1][1];
                    list.add(new int[]{left,right});
                    break;
                }
            }else if(newInterval[0]>right){
                list.add(new int[]{left,right});
                i++;
            }
        }
        if(newInterval[0]>right){
            list.add(new int[]{newInterval[0],newInterval[1]});
        }
        for(;i<intervals.length;i++){
            list.add(new int[]{intervals[i][0],intervals[i][1]});
        }
        return list.toArray(new int[0][0]);
    }
}
